#include<stdio.h>

void insertion_sort(int unsorted_array[], int num_elements);

void quick_sort(int unsorted_array[], int num_elements);

void heap_sort(int unsorted_array[], int num_elements);


void main() {
  int a[] = {1,9,8,7,6,5,0,2,3,4};
  printf("待排序序列: ");
  for (int m = 0; m < 10; ++m) {
    printf("%d ", a[m]);
  }
  printf("\n");

  insertion_sort(a, 10);

  printf("插入排序后: ");
  for(int i=0; i<10; i++) {
  printf("%d ", a[i]);
  }

  printf("\n\n"); //  此时应该看到输出为 0 1 2 3 4 5 6 7 8 9

  // 定义 int c[], int d[]，并初始化，用于测试quick_sort和heap_sort
  int c[] = {8,4,10,14,2,12,6,16,20,18};
  printf("待排序序列: ");
  for (int m = 0; m < 10; ++m) {
    printf("%d ", c[m]);
  }
  printf("\n");

  quick_sort(c, 10);

  printf("快速排序后: ");
  for(int i=0; i<10; i++) {
    printf("%d ", c[i]);
  }
  printf("\n\n"); //  此时应该看到输出为 2 4 6 8 10 12 14 16 18 20

  int d[] = {27,6,21,15,3,12,18,9,30,24};
  printf("待排序序列: ");
  for (int m = 0; m < 10; ++m) {
    printf("%d ", d[m]);
  }
  printf("\n");

  heap_sort(d, 10);

  printf("顶堆排序后: ");
  for(int i=0; i<10; i++) {
    printf("%d ", d[i]);
  }
  printf("\n\n"); //  此时应该看到输出为 3 6 9 12 15 18 21 24 27 30
}


void insertion_sort(int unsorted_array[], int num_elements){
  int temp;   //搞一个空杯子作为哨兵，相当于数组中unsorted_array[-1];
  int i, j;

  for (i= 2; i < num_elements; ++i) {
      if(unsorted_array[i] < unsorted_array[i-1]){
          temp = unsorted_array[i];
          unsorted_array[i] = unsorted_array[i-1];
          for (j = i-2; temp < unsorted_array[j]; --j) {
              unsorted_array[j+1] = unsorted_array[j];
          }
          unsorted_array[j+1] = temp;
      }
  }
}

//以下是快速排序的两个辅助函数
int Partition(int unsort_array[], int low, int high){   //partition意思为划分，分开。
  int temp = unsort_array[low];    //同样搞一个空杯子作为哨兵，相当于数组中unsorted_array[-1];
  int pivokey = unsort_array[low];
  while (low < high){
    while (low < high && unsort_array[high] >= pivokey) --high;
    unsort_array[low] = unsort_array[high];
    while (low < high && unsort_array[low] <= pivokey) ++low;
    unsort_array[high] = unsort_array[low];
  }
  unsort_array[low] = temp;
  return low;
}

void QSort(int unsorted_array[], int low, int high){
  if(low < high){
    int pivotic = Partition(unsorted_array, low, high);
    QSort(unsorted_array, low, pivotic-1);
    QSort(unsorted_array, pivotic+1, high);
  }
}

void quick_sort(int unsorted_array[], int num_elements){
  int low = 0,  high = num_elements-1;
  QSort(unsorted_array, low, high);
}
//以下为堆排序的辅助函数
void heap_adjust(int unsorted_array[], int s, int m){
  int node_record = unsorted_array[s-1];  //先对操作位置上的节点数据进行保存。
  for (int j = 2*s; j <= m; j*=2) {     //for循环找到值最大的孩子结点
    if(j<m && unsorted_array[j-1] <unsorted_array[j]) j++;
    if(node_record >= unsorted_array[j-1]) break;     //如果当前节点比最大的孩子节点还大，直接略过
    unsorted_array[s-1] = unsorted_array[j-1];          //如果当前节点比最大的孩子节点小，则将最大节点孩子替换为当前节点，并让当前节点为指向最大孩子节点位置
    s = j;
  }
  unsorted_array[s-1] = node_record;
}

void heap_sort(int unsorted_array[], int num_elements){
  int temp;
  //构建堆的过程
  for (int i = num_elements/2; i > 0 ; i--) {
    heap_adjust(unsorted_array, i, num_elements);
  }

  for (int i = num_elements; i >1 ; i--) {
    temp = unsorted_array[0];
    unsorted_array[0] = unsorted_array[i-1];
    unsorted_array[i-1] = temp;
    heap_adjust(unsorted_array, 1, i-1);
  }
}